int **res;
int *path, *used;
int pathlen, res_size;
int sum;

//类似0-1背包，累加和超过target就回溯并减去当前值，并排除掉组合问题的重复情况
void backtrace(int start, int* arr, int len, int k, int target, int** returnColumnSizes) {
    if (sum > target) return;
    if (sum == target && pathlen == k) {    //k数之和为target
            // printf("pathlen:%d\n", pathlen);
            // for (int j = 0; j < pathlen; j++) printf("%d ", path[j]);
            // printf("\n");

            //保存解
            res[res_size] = malloc(sizeof(int) * pathlen);
            memcpy(res[res_size], path, sizeof(int)*pathlen);
            (*returnColumnSizes)[res_size] = pathlen;
            res_size++;
            return ;
    }
    for (int i = start; i < len; i++) { // 组合问题，for中起始用start，前面的已经选过了
        //如果数组中有重复数字，则需要去重。同一层不能有两个相同数字
        // if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue; 
		   
        sum += arr[i];
        path[pathlen++] = arr[i];
        // used[i] = 1;
        backtrace(i+1, arr, len, k, target, returnColumnSizes); 
        sum -= arr[i];
        pathlen--;
        // used[i] = 0;
    }
}

int combinate(int n, int m)
 {
 	m = (m > n/2)? (n-m):m;
 	long ret = 1, m_fac = 1;
    int i;
    //例如：C10取3
    for (i = m; i > 1; i--) { //3!
        m_fac *= i;
    }
 	for (i = n; i > (n-m); i--) {  //10*9*8  
 		ret *= i;
 	}
     
 	ret /= m_fac;
 	return ret;
 }

// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
    int target = n;
    int nums[9] = {1,2,3,4,5,6,7,8,9};
    int len = 9, N = combinate(len, k); //组合情况有N种

    res = malloc(sizeof(int *) * N);
    *returnColumnSizes = malloc(sizeof(int)*N);
    path = malloc(sizeof(int) * len);
    // used = calloc(len, sizeof(int));
    pathlen = 0; res_size = 0; sum = 0;
    backtrace(0, nums, len, k, target, returnColumnSizes);

    *returnSize = res_size;
	free(path);
    return res;
}